package com.leetcode.partition14;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * @author rkc
 * @date 2022/8/23 9:02
 */
public class LC1329将矩阵按对角线排序_截距 {

    public int[][] diagonalSort(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        //对角线截距在[-(n - 1), m - 1]
        for (int b = - (n - 1); b <= m - 1; b++) {
            List<Integer> ls = new ArrayList<>();
            for (int x = 0, y = b; x < n && y < m; x++, y++) {
                if (y >= 0) {
                    ls.add(mat[x][y]);
                }
            }
            ls.sort(Comparator.naturalOrder());
            for (int x = 0, y = b, k = 0; x < n && y < m; x++, y++) {
                if (y >= 0) {
                    mat[x][y] = ls.get(k++);
                }
            }
        }
        return mat;
    }
}
